package NO8_Heap;


import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 2025-09-02
 * 力扣 - 215. 数组中的第K个最大元素
 * <p>
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 */
public class FindKthLargestMain {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(nums, 2));
        System.out.println(findKthLargest1(nums, 2));
    }

    public static int findKthLargest(int[] nums, int k) {
        // 使用最小堆，维护k个最大的元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // 移除最小的元素
            }
        }

        return minHeap.peek();
    }

    public static int findKthLargest1(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
